package dataS.SortMethod;
//重点学习
public class InsertSort {
    public static void main(String[] args) {
        InsertSort sort=new InsertSort();

        int[] a = new int[]{9,8,7,6,10};
        sort.insertSort3(a);
        for (int i : a) {
            System.out.print(i+" ");
        }
    }

    public void insertSort(int []ins){

        for(int i=1; i<ins.length; i++){
            int temp = ins[i];//保存每次需要插入的那个数
            int j;
            for(j=i; j>0&&ins[j-1]>temp; j--){
                ins[j] = ins[j-1];//吧大于需要插入的数往后移动。最后不大于temp的数就空出来j
            }
            ins[j] = temp;//将需要插入的数放入这个位置
        }
    }
    public void insertSort1(int []ins) {
        for (int i = 1; i < ins.length; i++) {
            for (int j = i; j > 0; j--) {
                if (ins[j] < ins[j - 1]) {
                    int temp = ins[j - 1];
                    ins[j - 1] = ins[j];
                    ins[j] = temp;
                }
            }
        }
    }
    public void insertSort2(int []nums){//适用于近乎有序，或者短，时间复杂度大大降低
        //将元素插入有序数组中，从最后一个开始，便移动边找位置直到没有元素大于temp

        int len=nums.length;
        for(int i=1;i<len;i++){
            int temp=nums[i];
            int j=i-1;
            //不确定循环次数用while
            while(j>=0&&nums[j]>temp){  //  02341   j=5
                nums[j+1]=nums[j];
                j--;
            }
            nums[j+1]=temp;
        }
    }
    public void insertSort3(int []nums){


        int len=nums.length;
        for(int i=1;i<len;i++){
            int temp=nums[i];
            int j=i;

            while(j>0&&nums[j-1]>temp){  //  02341   j=5
                nums[j]=nums[j-1];
                j--;
            }
            nums[j]=temp;
        }
    }

}
